1. Field of the Invention
Certain embodiments of the present invention are directed to methods of distributing datagrams across a network. Certain other embodiments of the present invention are directed to devices for implementing such methods.
2. Description of the Related Art
Telecommunications systems typically distribute information, usually in the form of datagrams such as, but not limited to, data cells and packets, over networks that include network devices such as, but not limited to, hosts, servers, modules, nodes, and distribution devices such as, but not limited to, switches and routers. A small portion of a representative network is illustrated in FIG. 1.
In FIG. 1, a switch or router 100, a first host 110, a second host 120, and a server 130 are all illustrated as being connected/linked to each other and to thereby form a portion of a network. The router 100 includes a plurality of ports. Among the plurality of ports, a first port 140 functions as an ingress port for a first datagram, illustrated as a first packet P1 in FIG. 1. The first packet P1 has been forwarded to the router 100 from a source that is not illustrated in FIG. 1.
A second port 150, also among the plurality of ports, is one possible egress for the data that came into the router 100 as part of the first packet P1. In a Layer-3 switching environment, upon egress from the router 100, the source address (SA) of the packet is changed to the router MAC address of the router 100. The destination address (DA) of the packet is changed to the next-hop address (NHA) or, in the example illustrated in FIG. 1, the address of the first host 110. The data egresses in the form of a second packet P2 from the router 100 to the first host 110.
A third port 160 is another potential egress port for the data that entered the router 100 through the first port 140. If the data egresses through the third port 160, it does so as a third datagram, illustrated as a third packet P3 in FIG. 1. The third packet P3 has a different SA than the first packet P1 and a different DA, or NHA, than the second packet P2, since the third packet's P3 next hop is to the second host 120 while the second packet's P2 next hop is to the first host 110. It should also be noted that other packet attributes, such as time-to-live (TTL) and Header Checksum typically change. It should also be noted that, in FIG. 1, the SA of the second packet P2 and third packet P3 will be the same, but different than the SA of the first packet P1.
Although many other factors frequently come into play, according to a simplified model, calculating the “cost” of a path in a network involves counting the number of “hops” that a datagram or packet has to make between a source and a destination. For example, in FIG. 1, an IP packet traveling from the router 100 to the server 130 may hop to either the first host 110 or second host 120 before hopping to the server 130. Since the number of hops are equivalent for the IP packet, regardless of whether it travels to the first host 110 or second host 120, the IP packet at the router 100 is said to have two equal-cost paths available to it.
According to this simplified model, since the router 100 relies exclusively upon the number of hops between it and the datagram or packet destination to determine the cost of a path, the router 100 can make no cost-based distinction between the path through the first host 110 and the path through the second host 120. Hence, in order to determine whether to forward the data in the first packet P1 as the second packet P2 or the third packet P3, the router 100 often makes use of an equal-cost multi-path (ECMP) algorithm, which is well know in the related art.
Unfortunately, although ECMP algorithms according to the related art are often useful for distributing traffic evenly over a set of equal-cost paths, ECMP algorithms according to the related art fail to account for general network traffic that also commonly flows through the various network devices along the equal-cost paths. Hence, in the partial network illustrated in FIG. 1, if the first host 110 has more general network traffic flowing across it than the second host 120, when the router 100 begins distributing packet traffic via the ECMP algorithm discussed above, then the first host 110 could become overly burdened with total traffic relative to the second host 120. Under such circumstances, the network devices are generally not utilized optimally and the network is not operating at maximum efficiency.
In addition to the general inability of ECMP algorithms according to the related art to account for general network traffic, these algorithms also typically require a considerable amount of distribution device resources. These resources are generally in the form of time allocated to performing the algorithms and in the form of hardware that is used and re-used while performing the algorithms.
At least in view of the above, there is a need for methods that are capable of distributing datagram, data, and/or packet traffic across equal-cost paths in a network in a manner that reduces the possibility that certain network devices along the equal-cost paths will be overly burdened. There is also a need for devices capable of implementing such methods.
In addition, at least in view of the above, there is also a need for methods that reduce the amount of time spent by the distribution device in performing lookup algorithms and/or that reduce the amount of hardware that is used and re-used while performing such algorithms. Further, there is a need for devices capable of implementing such methods.